//===--- Integers.swift.gyb -----------------------------------*- swift -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// RUN: rm -rf %t && mkdir -p %t && %S/../../utils/gyb -DWORD_BITS=%target-ptrsize %s -o %t/out.swift
// RUN: %S/../../utils/line-directive %t/out.swift -- %target-build-swift -parse-stdlib %t/out.swift -o %t/a.out -Onone
// RUN: %S/../../utils/line-directive %t/out.swift -- %target-run %t/a.out
// --stdlib-unittest-filter DoubleWidth/

// REQUIRES: executable_test

// FIXME: this test runs forever on iOS arm64
// REQUIRES: CPU=x86_64

import Swift

%{
#
# Utility code for later in this template
#
from math import log
from string import maketrans, capitalize

# Number of bits in the Builtin.Word type
word_bits = int(WORD_BITS) # int(CMAKE_SIZEOF_VOID_P) * 8

# Number of bits in integer literals.
builtinIntLiteralBits = 2048
IntLiteral = 'Int%s' % builtinIntLiteralBits

# 32-bit iOS simulator doesn't have Int128 support, so we stop at
# double-word.
fixedBitWidths = [x for x in [8, 16, 32, 64, 128] if x <= 2*word_bits]

class struct(object):
  def __init__(self, **kw):
    self.__dict__ = kw
  def __repr__(self):
    return 'struct(%r)' % self.__dict__

binaryArithmetic = [
    struct(operator='+', name='adding',      mutatingName='add',           firstArg='_',           llvmName='add', kind='+'),
    struct(operator='-', name='subtracting', mutatingName='subtract',      firstArg='_',           llvmName='sub', kind='-'),
    struct(operator='*', name='multiplied',  mutatingName='multiply',      firstArg='by',         llvmName='mul', kind='*'),
    struct(operator='/', name='divided',     mutatingName='divide',        firstArg='by',         llvmName='div', kind='/'),
    struct(operator='%', name='remainder',   mutatingName='formRemainder', firstArg='dividingBy', llvmName='rem', kind='/'),
]


binaryBitwise = [
    struct(operator='&', name='and'),
    struct(operator='|', name='or'),
    struct(operator='^', name='xor'),
]

maskingShifts = [
    struct(
      operator='&>>', nonMaskingOperator='>>',
      name='maskingShiftRight', llvmName=lambda s:['lshr','ashr'][s]),
    struct(
      operator='&<<', nonMaskingOperator='<<',
      name='maskingShiftLeft', llvmName=lambda _: 'shl'),
]
}%

//===--- Bits for the Stdlib ----------------------------------------------===//

extension Bool {
  @_transparent
  public init(_ value: Builtin.Int1) {
    self.init(_builtinBooleanLiteral: value)
  }

  @_transparent
  // Renamed from _value to __value, because the deserializer crashes
  // if stdlib is compiled with -sil-serialize-all (rdar://problem/23620491).
  // TODO: rename it back to _value when the deserializer is fixed.
  public var __value: Builtin.Int1 {
    return Builtin.trunc_Int${word_bits}_Int1((self ? 1 : 0)._value)
  }
}

// This should go in the stdlib separately, probably.
extension IntegerLiteralConvertible
  where Self : _BuiltinIntegerLiteralConvertible {
  /// Create an instance initialized to `value`.
  @_transparent
  public init(integerLiteral value: Self) {
    self = value
  }
}

infix operator &<< { associativity none precedence 160 }
infix operator &<<= { associativity right precedence 90 assignment }
infix operator &>> { associativity none precedence 160 }
infix operator &>>= { associativity right precedence 90 assignment }

@_transparent
public func _assertCond(
  @autoclosure _ condition: () -> Bool,
  @autoclosure _ message: () -> String,
  file: StaticString = #file, line: UInt = #line) {
  let ok = condition()
  if _isDebugAssertConfiguration() {
    precondition(ok, message, file: file, line: line)
  }
  Builtin.condfail((!ok).__value)
}

//===--- Prototype Implementation -----------------------------------------===//

/// Prints the message if the body is uncommented; used for
/// diagnostics.
@_transparent
public func _log(@autoclosure _ message: ()->String) {
  print(message())
}

//===----------------------------------------------------------------------===//
//===--- Arithmetic -------------------------------------------------------===//
//===----------------------------------------------------------------------===//

/// Arithmetic protocol declares methods backing binary arithmetic operators,
/// such as  `+`, `-` and `*`; and their mutating counterparts. These methods
/// operate on arguments of the same type.
///
/// Both mutating and non-mutating operations are declared in the protocol, but
/// only the mutating ones are required. Should conforming type omit
/// non-mutating implementations, they will be provided by a protocol extension.
/// Implementation in that case will copy `self`, perform a mutating operation
/// on it and return the resulting value.
public protocol Arithmetic {
  /// Initialize to zero
  init()

% for x in binaryArithmetic:
  // defaulted using an in-place counterpart, but can be used as an
  // optimization hook
  @warn_unused_result
  func ${x.name}(${x.firstArg} rhs: Self) -> Self

  // implementation hook
  mutating func ${x.mutatingName}(${x.firstArg} rhs: Self)
% end
}

extension Arithmetic {
% for x in binaryArithmetic:
%   callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
  public func ${x.name}(${x.firstArg} rhs: Self) -> Self {
    var lhs = self
    lhs.${x.mutatingName}(${callLabel}rhs)
    return lhs
  }
% end
}

/// SignedArithmetic protocol will only be conformed to by signed numbers,
/// otherwise it would be possible to negate an unsigned value.
///
/// The only method of this protocol has the default implementation in an
/// extension, that uses a parameterless initializer and subtraction.
public protocol SignedArithmetic : Arithmetic {
  func negate() -> Self
}

extension SignedArithmetic {
  public func negate() -> Self {
    return Self() - self
  }
}

% for x in binaryArithmetic:
%   callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
@_transparent
@warn_unused_result
public func ${x.operator} <T: Arithmetic>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}(${callLabel}rhs)
}

@_transparent
public func ${x.operator}= <T: Arithmetic>(lhs: inout T, rhs: T) {
  lhs.${x.mutatingName}(${callLabel}rhs)
}
% end

@_transparent
@warn_unused_result
public prefix func -<T: SignedArithmetic>(x: T) -> T {
  return x.negate()
}

//===----------------------------------------------------------------------===//
//===--- Integer ----------------------------------------------------------===//
//===----------------------------------------------------------------------===//
public typealias Word = Int${word_bits}
public typealias UWord = UInt${word_bits}

% IntegerBase = 'Comparable, Arithmetic, ' + \
%               'IntegerLiteralConvertible, CustomStringConvertible'

/// Integer protocol is a base for all the integer types that are available in
/// the standard library, and besides should be sufficient to implement
/// arbitrary precision integer types.
///
/// `isEqual(to:)` and `isLess(than:)` methods are the ones responsible for
/// `Equatable` and `Comparable` protocol conformances. In a way similar to how
/// arithmetic operations are dispatched in `Arithmetic`, `==` and `<` operators
/// for homogeneous comparisons have default implementations that call
/// `isEqual(to:)` and `isLess(than:)` respectively.
///
/// This protocol adds 3 new initializers to the parameterless one, inherited
/// from `Arithmetic`. These initializers allow to construct values of type
/// from instances of any other type, conforming to `Integer`, using different
/// strategies:
///   - Perform checks whether the value is representable in `Self`
///   - Try to represent the value without bounds checking
///   - Substitute values beyond `Self` bounds with maximum/minimum value of
///     `Self` respectively
public protocol Integer : ${IntegerBase} {

  // FIXME(compiler limitation): Ideally, this constraint would just be :
  // Integer.  Until we get recursive protocol requirements, that isn't
  // possible.

  /// A type that can hold absolute values of all the possible values of `Self`.
  /// Concrete types do not have to provide a typealias for it as it can be
  /// inferred from an `absoluteValue` property. This property (and type) can be
  /// useful in operations that are simpler to implement in terms of
  /// (potentially larger) unsigned values, for example, printing a value of an
  /// integer (it's just adding a '-' character in front of an absolute value).
  /// Please note, that `absoluteValue` property should not in general be used
  /// as a substitute for an `abs` free function, that returns a value of the
  /// same type.
  associatedtype AbsoluteValue : ${IntegerBase}

  static var isSigned: Bool { get }

  /// An absolute value of the represented number.
  ///
  /// Please note that `absoluteValue` has a different type than `self`, and so
  /// `abs(_:)` free function might be preferred for your use-case.
  var absoluteValue: AbsoluteValue { get }

  // Dispatching through these puts less stress on the user reading
  // the interface and error messages (and on the type checker) than
  // does having many operator overloads.
  @warn_unused_result
  func isEqual(to rhs: Self) -> Bool
  @warn_unused_result
  func isLess(than rhs: Self) -> Bool

  init<T : Integer>(_ source: T)
  init<T : Integer>(extendingOrTruncating source: T)
  init<T : Integer>(clamping source: T)

  /// Return n-th word in the underlying representation of `self`.
  @warn_unused_result
  func nthWord(_ n: Word) -> UWord

  /// A number of bits in current representation of `self`
  /// Will be constant for fixed-width integer types.
  var bitWidth : Word { get }

  /// If `self` is negative, returns the index of the least significant bit of
  /// our representation such that all more-significant bits are 1.
  /// Has the value -1 if `self` is 0.
  /// Has the value equal to `bitWidth - 1` for fixed width integers.
  var signBitIndex: Word { get }
}

extension Integer {
  public var countRepresentedWords: Word {
    return (self.bitWidth + ${word_bits} - 1) / ${word_bits}
  }
}

//===--- Homogeneous comparison -------------------------------------------===//
@_transparent
@warn_unused_result
public func == <T : Integer>(lhs:T, rhs: T) -> Bool {
  return lhs.isEqual(to: rhs)
}

@_transparent
@warn_unused_result
public func < <T : Integer>(lhs: T, rhs: T) -> Bool {
  return lhs.isLess(than: rhs)
}

//===--- Heterogeneous comparison -----------------------------------------===//
@_transparent
@warn_unused_result
public func == <T : Integer, U : Integer>(lhs:T, rhs: U) -> Bool {
  return (lhs > 0) == (rhs > 0)
    && T(extendingOrTruncating: rhs) == lhs
    && U(extendingOrTruncating: lhs) == rhs
}

@_transparent
@warn_unused_result
public func != <T : Integer, U : Integer>(lhs:T, rhs: U) -> Bool {
  return !(lhs == rhs)
}

@_transparent
@warn_unused_result
public func < <T : Integer, U : Integer>(lhs: T, rhs: U) -> Bool {
  let lhsSign = lhs < 0 ? -1 : lhs > 0 ? 1 : 0
  let rhsSign = rhs < 0 ? -1 : rhs > 0 ? 1 : 0
  if lhsSign != rhsSign { return lhsSign < rhsSign }

  // if we get here, lhs and rhs have the same sign.  If they're
  // negative, then T and U are both signed types, and one of them can
  // represent values of the other type.  Otherwise, lhs and rhs are
  // positive, and one of T, U may be signed and the other unsigned.
  // In this case, we can conceptually subtract 1 from the bitWidth of
  // any signed type, and either the resulting bitWidths are the same
  // or one can represent every value of the other.

  let rT = T(extendingOrTruncating: rhs)

  // Can we round-trip rhs through T?
  if U(extendingOrTruncating: rT) == rhs {
    return lhs < rT
  }

  return U(extendingOrTruncating: lhs) < rhs
}

@inline(__always)
@warn_unused_result
public func <= <T : Integer, U : Integer>(lhs: T, rhs: U) -> Bool {
  return !(rhs < lhs)
}

@inline(__always)
@warn_unused_result
public func >= <T : Integer, U : Integer>(lhs: T, rhs: U) -> Bool {
  return !(lhs < rhs)
}

@inline(__always)
@warn_unused_result
public func > <T : Integer, U : Integer>(lhs: T, rhs: U) -> Bool {
  return rhs < lhs
}

//===--- Ambiguity breakers -----------------------------------------------===//
// These two versions of the operators are not ordered with respect to
// one another:
//
//     <T : Comparable>(T,T) -> Bool
//     <T : Integer, U : Integer>(T,U) -> Bool
//
// so we define:
//
//     <T : Integer>(T,T) -> Bool

@_transparent
@warn_unused_result
public func != <T : Integer>(lhs:T, rhs: T) -> Bool {
  return !(lhs == rhs)
}

@inline(__always)
@warn_unused_result
public func <= <T : Integer>(lhs: T, rhs: T) -> Bool {
  return !(rhs < lhs)
}

@inline(__always)
@warn_unused_result
public func >= <T : Integer>(lhs: T, rhs: T) -> Bool {
  return !(lhs < rhs)
}

@inline(__always)
@warn_unused_result
public func > <T : Integer>(lhs: T, rhs: T) -> Bool {
  return rhs < lhs
}

//===----------------------------------------------------------------------===//
//===--- FixedWidthInteger ------------------------------------------------===//
//===----------------------------------------------------------------------===//
public enum ArithmeticOverflow {
  @_transparent
  public init(_ overflow: Bool) { self = overflow ? .overflow : .none }
  case none, overflow
}

/// A protocol for all the fixed width integer types. Main addition to the
/// `Integer` protocol is binary bitwise operations and bit shifts.
///
/// `WithOverflow` family of methods is used in default implementations of
/// mutating arithmetic methods (from `Arithmetic` protocol), provided by a
/// protocol extension. Having these methods allows to provide both safe
/// (trapping) and unsafe implementation of arithmetic operations without
/// duplicating code.
///
/// Bitwise binary and shift operators are implemented the same way as
/// arithmetic operations: free function dispatches a call to a corresponding
/// protocol method.
///
/// `doubleWidthMultiply` method is a necessary building block to implement
/// support for integer types of a greater width and as a consequence, arbitrary
/// precision integers.
public protocol FixedWidthInteger : Integer {
  static var bitWidth : Word { get }

  static var max: Self { get }
  static var min: Self { get }

% for x in binaryArithmetic:
%{
comment = '''
  /// Return a pair consisting of `self` {} `rhs`,
  /// truncated to fit if necessary, and a flag indicating whether an
  /// arithmetic overflow occurred.'''.format(x.operator) + ('''
  ///
  /// - Precondition: `rhs != 0`''' if x.kind == '/' else '')
}%
${comment}
  @warn_unused_result
  func ${x.name}WithOverflow(
    ${x.firstArg} rhs: Self
  ) -> (partialValue: Self, overflow: ArithmeticOverflow)
% end

% for x in binaryBitwise + maskingShifts:
  @warn_unused_result
  func ${x.name}(_ rhs: Self) -> Self
% end

  @warn_unused_result
  func doubleWidthMultiply(_ other: Self) -> (high: Self, low: AbsoluteValue)

  init(_truncatingBits bits: UWord)
}

% for x in binaryBitwise:
@warn_unused_result
@_transparent
public func ${x.operator} <T: FixedWidthInteger>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}(rhs)
}

@_transparent
public func ${x.operator}= <T: FixedWidthInteger>(lhs: inout T, rhs: T) {
  lhs = lhs.${x.name}(rhs)
}
% end

% for x in maskingShifts:
@warn_unused_result
@_transparent
public func ${x.operator} <T: FixedWidthInteger>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}(rhs)
}

@_transparent
public func ${x.operator}= <T: FixedWidthInteger>(lhs: inout T, rhs: T) {
  lhs = lhs ${x.operator} rhs
}

@warn_unused_result
@_transparent
public func ${x.operator} <
  T: FixedWidthInteger, U: Integer
>(lhs: T, rhs: U) -> T {
  return lhs.${x.name}(T(extendingOrTruncating: rhs))
}

@_transparent
public func ${x.operator}= <
  T: FixedWidthInteger, U: Integer
>(lhs: inout T, rhs: U) {
  lhs = lhs ${x.operator} rhs
}

@warn_unused_result
@_transparent
public func ${x.nonMaskingOperator} <
  T: FixedWidthInteger, U: Integer
>(lhs: T, rhs: U) -> T {
  let shift = rhs < -T.bitWidth ? -T.bitWidth
            : rhs > T.bitWidth ? T.bitWidth
            : Word(rhs)
  return lhs ${x.nonMaskingOperator} shift
}

// "Smart shift", supporting overshifts and negative shifts

@warn_unused_result
@_transparent
public func ${x.nonMaskingOperator} <
  T: FixedWidthInteger
>(lhs: T, rhs: Word) -> T {
  let overshiftR = T.isSigned ? lhs &>> (T.bitWidth - 1) : 0
  let overshiftL: T = 0
  if _fastPath(rhs >= 0) {
    if _fastPath(rhs < T.bitWidth) {
      return lhs.${x.name}(T(extendingOrTruncating: rhs))
    }
    return overshift${'LR'['R' in x.name]}
  }

  if _slowPath(rhs <= -T.bitWidth) {
    return overshift${'RL'['R' in x.name]}
  }
  return lhs ${x.operator.translate(maketrans('<>', '><'))} -rhs
}

@_transparent
public func ${x.nonMaskingOperator}= <
  T: FixedWidthInteger
>(lhs: inout T, rhs: T) {
  lhs = lhs ${x.nonMaskingOperator} rhs
}

@_transparent
public func ${x.nonMaskingOperator}= <
  T: FixedWidthInteger, U: Integer
>(lhs: inout T, rhs: U) {
  lhs = lhs ${x.nonMaskingOperator} rhs
}
% end

@warn_unused_result
@inline(__always)
public prefix func ~ <T: FixedWidthInteger>(x: T) -> T {
  return 0 &- x &- 1
}

extension FixedWidthInteger {
  public init<Other: Integer>(clamping source: Other) {
    if _slowPath(source < Self.min) {
      self = Self.min
    }
    else if _slowPath(source > Self.max) {
      self = Self.max
    }
    else { self = Self(extendingOrTruncating: source) }
  }

% for x in binaryArithmetic:
%   callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
  @_transparent
  public mutating func ${x.mutatingName}(${x.firstArg} rhs: Self) {
    let (result, overflow) = self.${x.name}WithOverflow(${callLabel}rhs)
    _assertCond(overflow == .none, "overflow in ${x.name}")
    self = result
  }

  /// Return `self ${x.operator} rhs`.  If an arithmetic overflow
  /// occurs, the behavior is undefined.
  ///
  /// Note: use this function to avoid the cost of overflow checking
  /// when you are sure that the operation won't overflow.
  @warn_unused_result
  @_transparent
  public func unsafe${capitalize(x.name)}(rhs: Self) -> Self {
    let (result, overflow) = self.${x.name}WithOverflow(${callLabel}rhs)

    if (overflow != .none) {
      if (_isDebugAssertConfiguration()) {
        _preconditionFailure("overflow in unsafe${capitalize(x.name)}")
      }
      else {
        Builtin.conditionallyUnreachable()
      }
    }
    return result
  }
% end

  @_transparent
  public init() {
    self = 0
  }

  @_transparent
  public init<T : Integer>(extendingOrTruncating source: T) {
    if Self.bitWidth <= ${word_bits} {
      self = Self.init(_truncatingBits: source.nthWord(0))
    }
    else {
      var result: Self = source < 0 ? ~0 : 0
      // start with the most significant word
      var n = source.countRepresentedWords
      while n >= 0 {
        // masking is OK here because this we have already ensured
        // that Self.bitWidth > ${word_bits}.  Not masking results in
        // infinite recursion.
        result &<<= ${word_bits}
        result |= Self(_truncatingBits: source.nthWord(n))
        n -= 1
      }

      self = result
    }
  }

  @_transparent
  public // transparent
  static var _highBitIndex: Self {
    return Self.init(_truncatingBits: UWord(Self.bitWidth._storage) &- 1)
  }
}

% for x in binaryArithmetic:
%   callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
%   if x.kind != '/':
@warn_unused_result
public func &${x.operator} <T: FixedWidthInteger>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}WithOverflow(${callLabel}rhs).partialValue
}
%   end
% end

//===----------------------------------------------------------------------===//
//===--- UnsignedInteger --------------------------------------------------===//
//===----------------------------------------------------------------------===//
public protocol UnsignedInteger : Integer {
  associatedtype AbsoluteValue : Integer
}

extension UnsignedInteger {
  @_transparent
  public var absoluteValue: Self { return self }

  @_transparent
  public static var isSigned: Bool { return false }

  public var description: String {
    if self == 0 {
      return "0"
    }

    let ascii0 = 48
    var buf: [UnicodeScalar] = []

    var x = self
    repeat {
      let r = x % 10
      x /= 10
      buf.append(
        UnicodeScalar(
          ascii0 + Swift.Int(Word(extendingOrTruncating: r)._storage)))
    }
    while x != 0
    return String(buf.reversed().lazy.map { Character($0) })
  }
}

extension UnsignedInteger where Self : FixedWidthInteger {
  @_transparent
  public init<T : Integer>(_ source: T) {
    _assertCond(
      source >= 0, "negative value \(source) not representable by \(Self.self)")
    let requiredBits = source.signBitIndex + 1
    _assertCond(
      requiredBits <= Self.bitWidth,
      "\(Self.self) cannot store all \(requiredBits)  bits "
      + "needed for unsigned representation of \(source)")
    self.init(extendingOrTruncating: source)
  }

  @_transparent
  public static var max: Self {
    return ~0
  }

  @_transparent
  public static var min: Self {
    return 0
  }

}

//===----------------------------------------------------------------------===//
//===--- SignedInteger ----------------------------------------------------===//
//===----------------------------------------------------------------------===//

public protocol SignedInteger : Integer, SignedArithmetic {
  associatedtype AbsoluteValue : Integer
}

extension SignedInteger {
  public var description: String {
    let base = String(absoluteValue)
    return self < 0 ? "-" + base : base
  }

  @_transparent
  public static var isSigned: Bool { return true }
}

extension SignedInteger where Self : FixedWidthInteger {
  @_transparent
  public init<T : Integer>(_ source: T) {
    let requiredBits = source.signBitIndex + (source >= 0 ? 2 : 1)
    _assertCond(
      requiredBits <= Self.bitWidth,
      "\(Self.self) cannot store all \(requiredBits) bits "
      + "needed for signed representation of \(source)")
    self.init(extendingOrTruncating: source)
  }

  @_transparent
  public static var max: Self {
    return ~min
  }

  @_transparent
  public static var min: Self {
    return -1 &<< Self._highBitIndex
  }
}

//===--- Concrete FixedWidthIntegers --------------------------------------===//

% for bits in fixedBitWidths:
%   for signed in True, False:
%     Self = ('Int%d' if signed else 'UInt%d') % bits
%     Unsigned = 'Signed' if signed else 'Unsigned'
%     u = 's' if signed else 'u'
%     U = 'U' if signed else ''
%     z = 's' if signed else 'z'
public struct ${Self}
  : FixedWidthInteger, ${Unsigned}Integer,
    _BuiltinIntegerLiteralConvertible {

  @_transparent
  public init(_builtinIntegerLiteral x: _MaxBuiltinIntegerType) {
    _storage = Builtin.truncOrBitCast_${IntLiteral}_Int${bits}(x)
    Builtin.condfail(
      Builtin.cmp_ne_${IntLiteral}(
        Builtin.${z}extOrBitCast_Int${bits}_${IntLiteral}(
          _storage), x))
  }

  @_transparent
  public init(bitPattern x: ${U}Int${bits}) {
    _storage = x._storage
  }

  @warn_unused_result
  public func isEqual(to rhs: ${Self}) -> Bool {
    return Bool(Builtin.cmp_eq_Int${bits}(_storage, rhs._storage))
  }

  @warn_unused_result
  public func isLess(than rhs: ${Self}) -> Bool {
    return Bool(Builtin.cmp_${u}lt_Int${bits}(_storage, rhs._storage))
  }

%       for x in binaryArithmetic:
%         callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
  /// Return a pair consisting of `self` ${x.operator} `rhs`,
  /// truncated to fit if necessary, and a flag indicating whether an
  /// arithmetic overflow occurred.
  @warn_unused_result
  @_transparent
  public func ${x.name}WithOverflow(
    ${x.firstArg} rhs: ${Self}
  ) -> (partialValue: ${Self}, overflow: ArithmeticOverflow) {

%         if x.kind == '/':
    // No LLVM primitives for checking overflow of division
    // operations, so we check manually.
    if _slowPath(
      rhs == 0
      ${'|| self == %s.min && rhs == -1' % Self if signed else ''}
    ) {
      return (partialValue: self, overflow: .overflow)
    }

    let (newStorage, overflow) = (
      Builtin.${u}${x.llvmName}_Int${bits}(self._storage, rhs._storage),
      false.__value)

%         else:

    let (newStorage, overflow)
    = Builtin.${u}${x.llvmName}_with_overflow_Int${bits}(
      self._storage, rhs._storage, false.__value)
%         end

    return (
      partialValue: ${Self}(newStorage),
      overflow: ArithmeticOverflow(Bool(overflow)))
  }
%       end

  @_transparent
  public init(_ _storage: Builtin.Int${bits}) {
    self._storage = _storage
  }

% for x in binaryBitwise:
  @warn_unused_result
  @_transparent
  public func ${x.name}(_ rhs: ${Self}) -> ${Self} {
    return ${Self}(
      Builtin.${x.name}_Int${bits}(self._storage, rhs._storage))
  }
% end

% for x in maskingShifts:
  @warn_unused_result
  @_transparent
  public func ${x.name}(_ rhs: ${Self}) -> ${Self} {
    let rhs_ = rhs & ${Self}._highBitIndex
    return ${Self}(
      Builtin.${x.llvmName(signed)}_Int${bits}(self._storage, rhs_._storage))
  }
% end

  @_transparent
  public static var bitWidth : Word { return ${bits} }

  public var bitWidth: Word { return ${bits} }

  @_transparent
  public var signBitIndex: Word {
% if signed:
    let x = self < 0 ? ~self : self
    return ${Self}.bitWidth - 1 - x.countLeadingZeros()
% else:
    return ${Self}.bitWidth - 1 - self.countLeadingZeros()
% end
  }


  @_transparent
  @warn_unused_result
  public func countLeadingZeros() -> Word {
    return Word(
      ${Self}(
        Builtin.int_ctlz_Int${bits}(self._storage, false.__value)
      )._lowUWord._storage)
  }

  @_transparent
  public func nthWord(_ n: Word) -> UWord {
    _precondition(n >= 0, "Negative word index")
    if _fastPath(n < countRepresentedWords) {
      let shift = UWord(n._storage) &* ${word_bits}
      let bitWidth = UWord(self.bitWidth._storage)
      _sanityCheck(shift < bitWidth)
      return (self &>> ${Self}(_truncatingBits: shift))._lowUWord
    }
    return self < 0 ? ~0 : 0
  }


  @_transparent
  public // transparent
  var _lowUWord: UWord {
    % truncOrExt = z + 'ext' if bits <= word_bits else 'trunc'
    return UWord(
      Builtin.${truncOrExt}OrBitCast_Int${bits}_Int${word_bits}(_storage)
    )
  }

  @_transparent
  public // transparent
  init(_truncatingBits bits: UWord) {
    % truncOrExt = 'zext' if bits > word_bits else 'trunc'
    self.init(
      Builtin.${truncOrExt}OrBitCast_Int${word_bits}_Int${bits}(bits._storage))
  }

% if signed:
  @_transparent
  public var absoluteValue: U${Self} {
    let base = U${Self}(_storage)
    return self < 0 ? ~base + 1 : base
  }
% end

%     dbits = bits*2
  @warn_unused_result
  public func doubleWidthMultiply(_ other: ${Self})
    -> (high: ${Self}, low: ${Self}.AbsoluteValue) {
%       if bits > 64:
    fatalError("${bits}-bit integer multiplication is not supported")
%       else:
    let lhs = Builtin.${z}ext_Int${bits}_Int${dbits}(self._storage)
    let rhs = Builtin.${z}ext_Int${bits}_Int${dbits}(other._storage)

    let res = Builtin.mul_Int${dbits}(lhs, rhs)
    let low = ${Self}.AbsoluteValue(Builtin.truncOrBitCast_Int${dbits}_Int${bits}(res))
    let shift: UInt8 = ${bits}
    let shifted = Builtin.ashr_Int${dbits}(res,
      Builtin.zextOrBitCast_Int8_Int${dbits}(shift._storage))
    let high = ${Self}(Builtin.truncOrBitCast_Int${dbits}_Int${bits}(shifted))
    return (high: high, low: low)
%       end
  }

  public var _storage: Builtin.Int${bits}
}

%   end
% end

//===--- Double width integer ---------------------------------------------===//
public struct DoubleWidth<
  T : FixedWidthInteger
  where
  T.AbsoluteValue : FixedWidthInteger,
  T.AbsoluteValue.AbsoluteValue == T.AbsoluteValue
> : FixedWidthInteger, _BuiltinIntegerLiteralConvertible {

  internal typealias High = T
  internal typealias Low = T.AbsoluteValue

  internal var _storage: (high: T, low: T.AbsoluteValue)

  internal init(_ _value: (High, Low)) {
    self._storage = (high: _value.0, low: _value.1)
  }

  // arithmetic
  //
  public init() {
    self.init((High(), Low()))
  }

  // integer
  //
  public var absoluteValue: DoubleWidth<Low> {
    if T.isSigned && _storage.high < 0 {
        return DoubleWidth<T>().subtracting(self).absoluteValue
    }
    return DoubleWidth<Low>((
      _storage.high.absoluteValue, _storage.low.absoluteValue))
  }

  @warn_unused_result
  public func isEqual(to rhs: DoubleWidth<T>) -> Bool {
    return (_storage.high == rhs._storage.high) &&
           (_storage.low == rhs._storage.low)
  }

  @warn_unused_result
  public func isLess(than rhs: DoubleWidth<T>) -> Bool {
    if _storage.high < rhs._storage.high {
      return true
    }
    if (_storage.high > rhs._storage.high) {
      return false
    }
    return _storage.low < rhs._storage.low
  }

  public init<T : Integer>(_ source: T) {
    fatalError()
  }

  public init<T : Integer>(extendingOrTruncating source: T) {
    fatalError()
  }

  @warn_unused_result
  public func nthWord(_ n: Word) -> UWord {
    if T.bitWidth < ${word_bits} || T.bitWidth % ${word_bits} != 0 {
      fatalError("nthWord is not supported on this type")
    }
    // TODO: move to Int128 just like init(_builtinIntegerLiteral:) ?
    let wordsInT = T.bitWidth / ${word_bits}
    return (n < wordsInT) ?
      _storage.low.nthWord(n) :
      _storage.high.nthWord(n - wordsInT)
  }

  public static var isSigned: Bool {
    return T.isSigned
  }

  public var bitWidth : Word {
    return 2 * T.bitWidth
  }

  public var signBitIndex: Word {
    return (self == DoubleWidth<T>()) ? -1 : (bitWidth - 1)
  }

  // fixed width
  //
  public static var max: DoubleWidth<T> {
    return self.init((High.max, Low.max))
  }

  public static var min: DoubleWidth<T> {
    return self.init((High.min, Low.min))
  }

  public static var bitWidth : Word { return 2 * T.bitWidth }

% for x in binaryArithmetic[:2]:
%   highAffectedByLowOverflow = 'T.max' if x.operator == '+' else 'T.min'
  public func ${x.name}WithOverflow(_ rhs: DoubleWidth<T>)
    -> (partialValue: DoubleWidth<T>, overflow: ArithmeticOverflow) {
    let (low, lowOverflow) =
      _storage.low.${x.name}WithOverflow(rhs._storage.low)
    let (high, highOverflow) =
      _storage.high.${x.name}WithOverflow(rhs._storage.high)
    let isLowOverflow = lowOverflow == .overflow
    let result = (high.${x.name}(isLowOverflow ? 1 : 0), low)
    let overflow = ArithmeticOverflow(
      highOverflow == .overflow ||
      high == ${highAffectedByLowOverflow} && isLowOverflow
    )
    return (partialValue: DoubleWidth<T>(result),
      overflow: overflow)
  }
% end


  @warn_unused_result
  public func multipliedWithOverflow(
    by rhs: DoubleWidth<T>
  ) -> (partialValue: DoubleWidth<T>, overflow: ArithmeticOverflow) {
    let isNegative = (self < DoubleWidth<T>()) != (rhs < DoubleWidth<T>())

    func mul(_ x: Low, _ y: Low, _ carry: Low) -> (partial: Low, carry: Low) {
      let pair = x.doubleWidthMultiply(y)
      let t = DoubleWidth<Low>(pair) + DoubleWidth<Low>((0, carry))
      return (partial: t._storage.low, carry: t._storage.high)
    }

    var high: Low = 0
    var low: Low = 0

    func mkResult(_ isOverflow: Bool)
      -> (partialValue: DoubleWidth<T>, overflow: ArithmeticOverflow) {

      // TODO: High() cast fails
      let result = DoubleWidth<T>((High(high), low))
      if isNegative {
        return DoubleWidth<T>().subtractingWithOverflow(result)
      }
      return (partialValue: result, overflow: ArithmeticOverflow(isOverflow))
    }

    var carry: Low = 0

    let lhs = self.absoluteValue
    let rhs = rhs.absoluteValue

    // TODO: gyb me!
    let a = mul(rhs._storage.low, lhs._storage.low, carry)
    low += a.partial
    carry = a.carry
    /*_log("(II) 1 (\(high), \(low)) carry: \(carry)")*/

    let b = mul(rhs._storage.low, lhs._storage.high, carry)
    high += b.partial
    carry = b.carry
    /*_log("(II) 2 (\(high), \(low)) carry: \(carry)")*/

    if carry != 0 {
      /*_log("(EE) overflow")*/
      return mkResult(true)
    }

    let c = mul(rhs._storage.high, lhs._storage.low, carry)
    low += c.partial
    carry = c.carry
    /*_log("(II) 3 (\(high), \(low)) carry: \(carry)")*/

    let d = mul(rhs._storage.high, lhs._storage.high, carry)
    high += d.partial
    carry = d.carry
    /*_log("(II) 4 (\(high), \(low)) carry: \(carry)")*/

    /*if (carry > 0) { _log("(EE) overflow") }*/
    return mkResult(carry > 0)
  }

% for x in binaryArithmetic[3:]:
  @warn_unused_result
  public func ${x.name}WithOverflow(
    ${x.firstArg} rhs: DoubleWidth<T>
  ) -> (partialValue: DoubleWidth<T>, overflow: ArithmeticOverflow) {
    fatalError()
  }
% end

  @warn_unused_result
  public func doubleWidthMultiply(_ other: DoubleWidth<T>)
    -> (high: DoubleWidth<T>, low: DoubleWidth<T>.AbsoluteValue) {
      fatalError()
  }

% for x in binaryBitwise + maskingShifts:
  @warn_unused_result
  public func ${x.name}(_ rhs: DoubleWidth<T>) -> DoubleWidth<T> {
    fatalError()
  }
% end

  public init(_truncatingBits bits: UWord) {
    fatalError()
  }

  // other
  //
  public init(_builtinIntegerLiteral x: _MaxBuiltinIntegerType) {
    fatalError("Method must be overridden")
  }

  public var description: String {
    return "(\(_storage.high), \(_storage.low))"
  }
}

//===--- Int128/UInt128 ---------------------------------------------------===//

% for Self in ['Int129', 'UInt129']:
%   signed = 'U' not in Self
%   Half = Self[:-3] + '64'
%   Unsigned = 'Signed' if signed else 'Unsigned'
%   u = 's' if signed else 'u'
%   U = 'U' if signed else ''
%   z = 's' if signed else 'z'
public struct ${Self}
  : FixedWidthInteger, ${Unsigned}Integer,
    _BuiltinIntegerLiteralConvertible {

  internal var _storage = DoubleWidth<${Half}>()

  public init(_builtinIntegerLiteral x: _MaxBuiltinIntegerType) {
    let storage = Builtin.truncOrBitCast_${IntLiteral}_Int128(x)
    Builtin.condfail(
      Builtin.cmp_ne_${IntLiteral}(
        Builtin.${z}extOrBitCast_Int128_${IntLiteral}(
          storage), x))

    fatalError()
  }

  public init(bitPattern x: ${U}Int${bits}) {
    fatalError()
  }

  @warn_unused_result
  public func isEqual(to rhs: ${Self}) -> Bool {
    return _storage.isEqual(to: rhs._storage)
  }

  @warn_unused_result
  public func isLess(than rhs: ${Self}) -> Bool {
    return _storage.isLess(than: rhs._storage)
  }

%   for x in binaryArithmetic:
%     callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
  /// Return a pair consisting of `self` ${x.operator} `rhs`,
  /// truncated to fit if necessary, and a flag indicating whether an
  /// arithmetic overflow occurred.
  @warn_unused_result
  public func ${x.name}WithOverflow(
    ${x.firstArg} rhs: ${Self}
  ) -> (partialValue: ${Self}, overflow: ArithmeticOverflow) {
    fatalError()
  }
%   end

% for x in binaryBitwise:
  @warn_unused_result
  @_transparent
  public func ${x.name}(_ rhs: ${Self}) -> ${Self} {
    fatalError()
  }
% end

% for x in maskingShifts:
  @warn_unused_result
  @_transparent
  public func ${x.name}(_ rhs: ${Self}) -> ${Self} {
    fatalError()
  }
% end

  public static var bitWidth : Word { return 128 }

  public var bitWidth: Word { return 128 }

  public var signBitIndex: Word {
    return _storage.signBitIndex
  }

  @warn_unused_result
  public func countLeadingZeros() -> Word {
    fatalError()
  }

  public func nthWord(_ n: Word) -> UWord {
    _precondition(n >= 0, "Negative word index")
    return _storage.nthWord(n)
  }

  public // transparent
  init(_truncatingBits bits: UWord) {
    fatalError()
  }

% if signed:
  public var absoluteValue: U${Self} {
    return U${Self}(_storage.absoluteValue)
  }
% end

  @warn_unused_result
  public func doubleWidthMultiply(_ other: ${Self})
    -> (high: ${Self}, low: ${Self}.AbsoluteValue) {
    let (high: high, low: low) = _storage.doubleWidthMultiply(other._storage)
    return (high: ${Self}(high), low: ${Self}.AbsoluteValue(low))
  }

  internal init(_ _storage: DoubleWidth<${Half}>) {
    self._storage = _storage
  }

}
% end

//===--- Tests ------------------------------------------------------------===//

extension FixedWidthInteger {
  // @_transparent
  public mutating func replaceUWord(_ n: Word, with newBits: UWord) -> Bool {
    let flippedBits = nthWord(n) ^ newBits
    self ^= Self(_truncatingBits: flippedBits) << (${word_bits} * n)
    if nthWord(n) != newBits {
      _log("###### overflow replacing word \(n) with \(newBits.hex)")
    }
    return nthWord(n) == newBits
  }

  /// a hex representation of every bit in the number
  func hexBits(_ bitWidth: Word) -> String {
    let hexDigits: [UnicodeScalar] = [
      "0", "1", "2", "3", "4", "5", "6", "7",
      "8", "9", "A", "B", "C", "D", "E", "F"]

    var result = "".unicodeScalars
    var x = self
    var nibbles: Word = 0
    repeat {
      if nibbles % 4 == 0 && nibbles != 0 {
        result.insert("_", at: result.startIndex)
      }
      let lowUWord = x.nthWord(0)
      result.insert(
        hexDigits[Swift.Int(lowUWord._storage) & 0xF],
        at: result.startIndex
      )
      x.replaceUWord(0, with: lowUWord & ~0xF)
      x /= 16
      nibbles += 1
    }
    while (nibbles << 2 < bitWidth || (x != 0 && x + 1 != 0))
    return (self < 0 ? "[-]" : "[+]") + String(result)
  }

  var hex: String { return hexBits(0) }
}

typealias DWord = Int${word_bits*2}
typealias UDWord = UInt${word_bits*2}

import StdlibUnittest


func expectEqual<T : FixedWidthInteger>(
  _ expected: T, _ actual: T,
  @autoclosure _ message: () -> String = "",
  showFrame: Bool = true,
  stackTrace: SourceLocStack = SourceLocStack(),
  file: String = #file, line: UInt = #line
) {
  if expected != actual {
    expectationFailure(
      "expected: \(String(reflecting: expected))"
      + " (of type \(String(reflecting: expected.dynamicType)))\n"
      + "  = \(expected.hex)\n"
      + "actual: \(String(reflecting: actual))"
      + " (of type \(String(reflecting: actual.dynamicType)))\n"
      + "  = \(actual.hex)\n",
      trace: message(),
      stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
  }
}

func expectEqual<T : FixedWidthInteger>(
  _ expected: (T, ArithmeticOverflow), _ actual: (T, ArithmeticOverflow),
  @autoclosure _ message: () -> String = "",
  showFrame: Bool = true,
  stackTrace: SourceLocStack = SourceLocStack(),
  file: String = #file, line: UInt = #line
) {
% for i in 0, 1:
  expectEqual(
    expected.${i}, actual.${i}, message(),
    showFrame: false,
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
% end
}

var tests = TestSuite("Integers")

tests.test("Literals") {
  // Testing against the official Int types so as not to depend on
  // unimplemented stuff.
  let a: UInt8 = 0b1_0_11_0_111
  expectEqual(unsafeBitCast(a, to: Swift.UInt8.self), 0b1_0_11_0_111)

  let b: Int16 = 183
  expectEqual(unsafeBitCast(b, to: Swift.Int16.self), 0b1_0_11_0_111)

  let c: Int16 = -183
  expectEqual(unsafeBitCast(c, to: Swift.Int16.self), -183)

  let d: Int8 = 127
  expectEqual(unsafeBitCast(d, to: Swift.Int8.self), 127)

  let e: UInt8 = 255
  expectEqual(unsafeBitCast(e, to: Swift.UInt8.self), 255)
}

tests.test("Signed Literal Trap") {
  expectCrashLater()
  let _: Int8 = 128
}

tests.test("Unsigned Literal Trap") {
  expectCrashLater()
  let _: UInt8 = 256
}

tests.test("Equality") {
  expectEqual(183 as UInt8, 183)
  expectNotEqual(183 as UInt8, 184)

  expectEqual(49 as Int8, 49)
  expectNotEqual(-49 as Int8, 49)
}

func indexOrder<T: RandomAccessIndex>(_ x: T, y: T)
  -> ExpectedComparisonResult {
  return x < y ? .lt : x > y ? .gt : .eq
}

tests.test("Ordering") {
  checkComparable([127, 183, 184, 255] as [UInt8], oracle: indexOrder)
  checkComparable([-128, -1, 83, 84, 127] as [Int8], oracle: indexOrder)
  checkComparable([127, 183, 184, 255, 65535] as [UInt16], oracle: indexOrder)
  checkComparable([-32768, -32767, 83, 84, 32767] as [Int16], oracle: indexOrder)
}

tests.test("Simple-Arithmetic") {
  expectEqual(1 as Int8 + 2, 3)
  expectEqual(1 as Int8 - 2, -1)
  expectEqual(-5 as Int8 + 11, 6)
  expectEqual(3 as Int8 * 4, 12)
  expectEqual(4 as Int8 * -7, -28)
  expectEqual(-4 as Int8 * -7, 28)
  expectEqual(5 as Int8 / 2, 2)
  expectEqual(6 as Int8 / 2, 3)
  expectEqual(7 as Int8 / 2, 3)
  expectEqual(5 as Int8 % 3, 2)
  expectEqual(6 as Int8 % 3, 0)
  expectEqual(7 as Int8 % 3, 1)
}

% for w in fixedBitWidths:
%   for prefix in ['U', '']:
%     Type = '{}Int{}'.format(prefix, w)
tests.test("${Type}/Add/Overflow") {
  expectCrashLater()
  let _ = ${Type}.max + 1
}

tests.test("${Type}/Subtract/Underflow") {
  expectCrashLater()
  let _ = ${Type}.min - 1
}

tests.test("${Type}/AddInPlace/Overflow") {
  expectCrashLater()
  var x = ${Type}.max
  x += 1
}

tests.test("${Type}/SubtractInPlace/Underflow") {
  expectCrashLater()
  var x = ${Type}.min
  x -= 1
}
%   end
% end

tests.test("Simple-Bitwise") {
  expectEqual(0b100_1001 as Int8 >> 1, 0b10_0100)
  expectEqual(-0b100_1001 as Int8 >> 1, -0b10_0101)
  expectEqual(0b1011_0111 as UInt8 >> 1, 0b0101_1011)

  expectEqual(0b100_1001 as Int8 >> 1, 0b10_0100)
  expectEqual(-0b100_1001 as Int8 >> 1, -0b10_0101)
  expectEqual(0b1011_0111 as UInt8 >> 1, 0b0101_1011)

  expectEqual(0b1011_0111 as UInt8 & 0b0110_1110, 0b0010_0110)
  expectEqual(0b1011_0111 as UInt8 | 0b0110_1110, 0xFF)
  expectEqual(0b1011_0111 as UInt8 ^ 0b0110_1110, 0b1101_1001)
}

tests.test("MinMax") {
  expectEqual(255, UInt8.max)
  expectEqual(0, UInt8.min)
  expectEqual(127, Int8.max)
  expectEqual(-128, Int8.min)
}

tests.test("CountLeadingZeros") {
  expectEqual(0, UInt8.max.countLeadingZeros())
  expectEqual(8, UInt8.min.countLeadingZeros())
  expectEqual(1, Int8.max.countLeadingZeros())
  expectEqual(0, Int8.min.countLeadingZeros())
}

tests.test("signBitIndex") {
  expectEqual(7, UInt8.max.signBitIndex)
  expectEqual(-1, UInt8.min.signBitIndex)
  expectEqual(6, Int8.max.signBitIndex)
  expectEqual(-1, (0 as Int8).signBitIndex)
  expectEqual(6, Int8.min.signBitIndex)
}

tests.test("Conversion8to16") {
  expectEqual(255, UInt16(UInt8.max))
  expectEqual(255, Int16(UInt8.max))
  expectEqual(0, UInt16(UInt8.min))
  expectEqual(0, Int16(UInt8.min))
  expectEqual(127, Int16(Int8.max))
  let negativeValue = Int8.min
  expectCrashLater()
  _ = UInt16(negativeValue)
}


tests.test("Conversion16to8") {
  expectEqual(255, UInt8(255 as UInt16))
  expectEqual(255, UInt8(255 as Int16))

  expectEqual(0, UInt8(0 as UInt16))
  expectEqual(0, UInt8(0 as Int16))

  expectEqual(127, Int8(127 as UInt16))
  expectEqual(127, Int8(127 as Int16))

  expectEqual(-128, Int8(-128 as Int16))
  let tooLarge: UInt16 = 128
  expectCrashLater()
  _ = Int8(tooLarge)
}

tests.test("Conversion16to8a") {
  let tooLarge: Int16 = 128
  expectCrashLater()
  _ = Int8(tooLarge)
}

tests.test("Conversion16to8b") {
  let tooLarge: Int16 = 256
  expectCrashLater()
  _ = UInt8(tooLarge)
}

tests.test("Conversion16to8c") {
  let tooLarge: UInt16 = 256
  expectCrashLater()
  _ = UInt8(tooLarge)
}

tests.test("ConversionWordToDWord") {
  expectEqual(1 << ${word_bits} - 1, UDWord(UWord.max))
  expectEqual(1 << ${word_bits} - 1, DWord(UWord.max))
  expectEqual(0, UDWord(UWord.min))
  expectEqual(0, DWord(UWord.min))
  expectEqual(1 << ${word_bits-1} - 1, DWord(Word.max))
  let negativeValue = Word.min
  expectCrashLater()
  _ = UDWord(negativeValue)
}

tests.test("ConversionDWordToWord") {
  expectEqual(~0, UWord(1 << ${word_bits} - 1 as UDWord))
  expectEqual(~0, UWord(1 << ${word_bits} - 1 as DWord))

  expectEqual(0, UWord(0 as UDWord))
  expectEqual(0, UWord(0 as DWord))

  expectEqual(Word.max, Word(1 << ${word_bits-1} - 1 as UDWord))
  expectEqual(Word.max, Word(1 << ${word_bits-1} - 1 as DWord))

  expectEqual(Word.min, Word(-1 << ${word_bits-1} as DWord))
  let tooLarge: UDWord = 1 << ${word_bits-1}
  expectCrashLater()
  _ = Word(tooLarge)
}

tests.test("ConversionDWordToWordA") {
  let tooLarge: DWord = 1 << ${word_bits}
  expectCrashLater()
  _ = Word(tooLarge)
}

tests.test("ConversionDWordToWordB") {
  let tooLarge: DWord = 1 << ${word_bits}
  expectCrashLater()
  _ = UWord(tooLarge)
}

tests.test("ConversionDWordToWordC") {
  let tooLarge: UDWord = 1 << ${word_bits}
  expectCrashLater()
  _ = UWord(tooLarge)
}

tests.test("extendingOrTruncating") {

  expectEqual(-2, Int8(extendingOrTruncating: UInt8.max - 1))
  expectEqual(3, Int8(extendingOrTruncating: 3 as UInt8))
  expectEqual(UInt8.max - 1, UInt8(extendingOrTruncating: -2 as Int8))
  expectEqual(3, UInt8(extendingOrTruncating: 3 as Int8))

  expectEqual(-2, DWord(extendingOrTruncating: UDWord.max - 1))
  expectEqual(3, DWord(extendingOrTruncating: 3 as UDWord))
  expectEqual(UDWord.max - 1, UDWord(extendingOrTruncating: -2 as DWord))
  expectEqual(3, UDWord(extendingOrTruncating: 3 as DWord))

  expectEqual(-2, Int32(extendingOrTruncating: -2 as Int8))
  expectEqual(3, Int32(extendingOrTruncating: 3 as Int8))
  expectEqual(127, Int32(extendingOrTruncating: 127 as UInt8))
  expectEqual(129, Int32(extendingOrTruncating: 129 as UInt8))
  expectEqual((1 << 31 - 1) << 1, UInt32(extendingOrTruncating: -2 as Int8))
  expectEqual(3, UInt32(extendingOrTruncating: 3 as Int8))
  expectEqual(128, UInt32(extendingOrTruncating: 128 as UInt8))
  expectEqual(129, UInt32(extendingOrTruncating: 129 as UInt8))

  expectEqual(-2, DWord(extendingOrTruncating: -2 as Int8))
  expectEqual(3, DWord(extendingOrTruncating: 3 as Int8))
  expectEqual(127, DWord(extendingOrTruncating: 127 as UInt8))
  expectEqual(129, DWord(extendingOrTruncating: 129 as UInt8))
  expectEqual(
    (1 << ${word_bits*2-1} - 1) << 1,
    UDWord(extendingOrTruncating: -2 as Int8))
  expectEqual(3, UDWord(extendingOrTruncating: 3 as Int8))
  expectEqual(128, UDWord(extendingOrTruncating: 128 as UInt8))
  expectEqual(129, UDWord(extendingOrTruncating: 129 as UInt8))

  expectEqual(-2, Int8(extendingOrTruncating: -2 as DWord))
  expectEqual(-2, Int8(extendingOrTruncating: -1 << 67 - 2 as DWord))
  expectEqual(127, Int8(extendingOrTruncating: 127 as UDWord))
  expectEqual(-127, Int8(extendingOrTruncating: 129 as UDWord))
  expectEqual(0b1111_1100, UInt8(extendingOrTruncating: -4 as DWord))
  expectEqual(0b1111_1100, UInt8(extendingOrTruncating: -1 << 67 - 4 as DWord))
  expectEqual(128, UInt8(extendingOrTruncating: 128 + 1024 as UDWord))
  expectEqual(129, UInt8(extendingOrTruncating: 129 + 1024 as UDWord))
}

tests.test("HeterogeneousEquality") {
  expectTrue(-1 as DWord != UDWord.max)
  expectTrue(DWord.max == UDWord.max / 2)
  expectTrue((0 as DWord) == 0 as UDWord)

  expectTrue(-1 as Int8 == -1 as DWord)
  expectTrue(UInt8.max != -1 as DWord)
  expectTrue(UInt8.max == 255 as DWord)
  expectTrue((0 as UInt8) == 0 as DWord)

  expectTrue(UInt8.max == 255 as UDWord)
  expectTrue(UInt8.max != UDWord.max)
  expectTrue((0 as UInt8) == (0 as UDWord))
}

tests.test("HeterogeneousOrdering") {
  expectTrue((-1 as DWord) < UDWord.max)
  expectTrue(DWord.max <= UDWord.max / 2)
  expectTrue(DWord.max >= UDWord.max / 2)
  expectTrue((0 as DWord) <= (0 as UDWord))
  expectTrue((0 as DWord) >= (0 as UDWord))

  expectTrue((-1 as Int8) <= -1 as DWord)
  expectTrue((-1 as Int8) >= -1 as DWord)
  expectTrue(UInt8.max > -1 as DWord)
  expectTrue(UInt8.max <= 255 as DWord)
  expectTrue(UInt8.max >= 255 as DWord)
  expectTrue((0 as UInt8) <= (0 as DWord))
  expectTrue((0 as UInt8) >= (0 as DWord))

  expectTrue(UInt8.max <= 255 as UDWord)
  expectTrue(UInt8.max >= 255 as UDWord)
  expectTrue(UInt8.max < UDWord.max)
  expectTrue((0 as UInt8) <= (0 as UDWord))
  expectTrue((0 as UInt8) >= (0 as UDWord))
}

tests.test("SmartBitShift/Homogeneous/Left/Int16") {
  let all1s = ~0 as Int16
  expectEqual(all1s, all1s << (0 as Int16))
  expectEqual(-2, all1s << (1 as Int16))
  expectEqual(Int16.min, all1s << (15 as Int16))
  expectEqual(0, all1s << (16 as Int16))

  expectEqual(-1, all1s << (-1 as Int16))
  expectEqual(-1, all1s << (-15 as Int16))
  expectEqual(-1, all1s << (-16 as Int16))
}

tests.test("SmartBitShift/Unconstrained/Left/Int16") {
  let all1s = ~0 as Int16
  expectEqual(all1s, all1s << 0)
  expectEqual(-2, all1s << 1)
  expectEqual(Int16.min, all1s << 15)
  expectEqual(0, all1s << 16)

  expectEqual(-1, all1s << -1)
  expectEqual(-1, all1s << -15)
  expectEqual(-1, all1s << -16)
}

tests.test("SmartBitShift/Homogeneous/Left/UInt16") {
  let all1s = ~0 as UInt16
  expectEqual(all1s, all1s << 0)
  expectEqual(0b1111_1111_1111_1110, all1s << 1)
  expectEqual(UInt16.max / 2 + 1, all1s << 15)
  expectEqual(0, all1s << 16)
}

tests.test("SmartBitShift/Heterogeneous/Left/Int16") {
  let all1s = ~0 as Int16
  expectEqual(all1s, all1s << (0 as Int8))
  expectEqual(-2, all1s << (1 as Int32))
  expectEqual(Int16.min, all1s << (15 as UInt32))
  expectEqual(0, all1s << (16 as UInt8))

  expectEqual(-1, all1s << (-1 as DWord))
  expectEqual(-1, all1s << (-15 as Word))
  expectEqual(-1, all1s << (-16 as Int32))
}

tests.test("SmartBitShift/Heterogeneous/Left/UInt16") {
  let all1s = ~0 as UInt16
  expectEqual(all1s, all1s << (0 as Int8))
  expectEqual(0b1111_1111_1111_1110, all1s << (1 as Int32))
  expectEqual(UInt16.max / 2 + 1, all1s << (15 as UInt32))
  expectEqual(0, all1s << (16 as UInt8))

  expectEqual(UInt16.max / 2, all1s << (-1 as DWord))
  expectEqual(1, all1s << (-15 as Word))
  expectEqual(0, all1s << (-16 as Int32))
}

tests.test("SmartBitShift/Unconstrained/Left/UInt16") {
  let all1s = ~0 as UInt16
  expectEqual(all1s, all1s << 0)
  expectEqual(0b1111_1111_1111_1110, all1s << 1)
  expectEqual(UInt16.max / 2 + 1, all1s << 15)
  expectEqual(0, all1s << 16)

  expectEqual(UInt16.max / 2, all1s << -1)
  expectEqual(1, all1s << -15)
  expectEqual(0, all1s << -16)
}

tests.test("Basics") {

  expectEqual(sizeof(Word.self), sizeof(Swift.Int.self))
  expectEqual(sizeof(DWord.self), 2 * sizeof(Swift.Int.self))

  typealias I8 = UInt8
  let b8: I8 = 0b1_0_11_0_111
  expectEqual(b8, 0b1_0_11_0_111)
  expectEqual(b8, 183)
  expectNotEqual(b8, I8())
  expectEqual(I8(), 0)
  expectEqual(8, I8.bitWidth)
  expectEqual(16, Int16.bitWidth)
  expectEqual(32, Int32.bitWidth)
}

tests.test("nthWord") {
  let x = UDWord(Word.max)
  expectEqual(Word.max._lowUWord, x.nthWord(0))
  expectEqual(0, x.nthWord(1))

  let y = DWord(Word.min)
  expectEqual(Word.min._lowUWord, y.nthWord(0))
  expectEqual(~0, y.nthWord(1))

  let z = UWord(~Word.min) + 1
  expectEqual(Word.min._lowUWord, z.nthWord(0))
  expectEqual(0, z.nthWord(1))
}

tests.test("DoubleWidthMultiply/UInt8") {
  let a: UInt8 = 42
  let b: UInt8 = 42
  let res = a.doubleWidthMultiply(b)
  expectEqual(0x06, res.high)
  expectEqual(0xe4, res.low)
}

tests.test("DoubleWidthMultiply/Int8") {
  let a: Int8 = 42
  let b: Int8 = -42
  let res = a.doubleWidthMultiply(b)
  expectEqual(Int8(bitPattern: 0xf9), res.high)
  expectEqual(0x1c, res.low)
}

tests.test("DoubleWidthMultiply/Int8/DoubleNegation") {
  let a: Int8 = -42
  let b: Int8 = -42
  let res = a.doubleWidthMultiply(b)
  expectEqual(0x06, res.high)
  expectEqual(0xe4, res.low)
}

tests.test("DoubleWidth/Int8/isEqual") {
  let a = DoubleWidth<Int8>()
  let b = DoubleWidth<Int8>()
  expectEqual(a, b)
}

tests.test("DoubleWidth/Int8/not equal") {
  let a = DoubleWidth<Int8>()
  let b = DoubleWidth<Int8>((40, 2))
  expectNotEqual(a, b)
}

tests.test("DoubleWidth/Int8/isLess(than:)") {
  let a = DoubleWidth<Int8>.min
  let z = DoubleWidth<Int8>()
  let b = DoubleWidth<Int8>.max
  expectTrue(a < z)
  expectTrue(z < b)
  expectTrue(a < b)
}

tests.test("DoubleWidth/Int8/adding") {
  let a = DoubleWidth<Int8>((40, 2))
  let b = DoubleWidth<Int8>((2, 40))
  let res = a + b
  expectEqual(res._storage.high, 42)
  expectEqual(res._storage.low, 42)
}

tests.test("DoubleWidth/Int8/subtracting") {
  let a = DoubleWidth<Int8>((80, 4))
  let b = DoubleWidth<Int8>((40, 2))
  let res = a - b
  expectEqual(res._storage.high, 40)
  expectEqual(res._storage.low, 2)
}

tests.test("DoubleWidth/Int8/adding negative") {
  let a = DoubleWidth<Int8>((-1, 0xff))
  let b = DoubleWidth<Int8>((0, 1))
  let res = a + b
  expectEqual(res._storage.high, 0)
  expectEqual(res._storage.low, 0)
}

% for Type in ['Int8', 'Int16', 'Int32', 'Int64']:
tests.test("DoubleWidth/U${Type}/adding min and max") {
  let a = DoubleWidth<U${Type}>.max
  let b = DoubleWidth<U${Type}>.min
  let res = a + b
  expectEqual(res, DoubleWidth<U${Type}>.max)
}

tests.test("DoubleWidth/${Type}/adding min and max") {
  let a = DoubleWidth<${Type}>.max
  let b = DoubleWidth<${Type}>.min
  let res = a + b
  expectEqual(res, DoubleWidth<${Type}>((-1, ${Type}.AbsoluteValue.max)))
}

%   for s in ['', 'U']:
%     SType = s + Type
tests.test("DoubleWidth/${SType}/adding beyond max") {
  let a = DoubleWidth<${SType}>.max
  let b = DoubleWidth<${SType}>((0, 1))
  expectCrashLater()
  _ = a + b
}

tests.test("DoubleWidth/${SType}/subtracting beyond min") {
  let a = DoubleWidth<${SType}>.min
  let b = DoubleWidth<${SType}>((0, 1))
  expectCrashLater()
  _ = a - b
}

%   end
% end

tests.test("DoubleWidth/signBitIndex") {
  expectEqual(15, DoubleWidth<UInt8>.max.signBitIndex)
  expectEqual(-1, DoubleWidth<UInt8>.min.signBitIndex)
}

tests.test("DoubleWidth/UInt64/nthWord") {
  let x = DoubleWidth<UInt64>((0xdeadbeeffeebdaed, 0xcafebabeebabefac))
% if word_bits == 32:
  expectEqual(x.nthWord(1), 0xcafebabe)
  expectEqual(x.nthWord(3), 0xdeadbeef)
  expectEqual(x.nthWord(4), 0)
% elif word_bits == 64:
  expectEqual(x.nthWord(0), 0xcafebabeebabefac)
  expectEqual(x.nthWord(1), 0xdeadbeeffeebdaed)
  expectEqual(x.nthWord(2), 0)
% end
}

tests.test("DoubleWidth/Int8/absoluteValue negative") {
  let x = DoubleWidth<Int8>((-1, 0xff))
  expectEqual(x.absoluteValue, DoubleWidth<UInt8>((0, 1)))
}

tests.test("DoubleWidth/Int8/absoluteValue zero") {
  let x = DoubleWidth<Int8>((0, 0))
  expectEqual(x.absoluteValue, DoubleWidth<UInt8>((0, 0)))
}

tests.test("DoubleWidth/Int8/absoluteValue positive") {
  let x = DoubleWidth<Int8>((0, 0xff))
  expectEqual(x.absoluteValue, DoubleWidth<UInt8>((0, 0xff)))
}

tests.test("DoubleWidth/UInt8/absoluteValue") {
  let x = DoubleWidth<UInt8>((0, 1))
  expectEqual(x.absoluteValue, DoubleWidth<UInt8>((0, 1)))
}

tests.test("DoubleWidth/UInt8/multiply overflow") {
  let a = DoubleWidth<UInt8>((127, 0))
  let b = DoubleWidth<UInt8>((0, 2))
  let res = a * b
  expectEqual(res, DoubleWidth<UInt8>((254, 0)))
}

tests.test("DoubleWidth/Int8/multiply") {
  let a = DoubleWidth<Int8>((-2, 0xff))
  let b = DoubleWidth<Int8>((0, 2))
  let res = a * b
  expectEqual(res, DoubleWidth<Int8>((-3, 254)))
}


runAllTests()
